package leetcode_300;

import java.util.LinkedList;
import java.util.Queue;

/**
 *@author 周杨
 *CourseScheduleII_210 拓扑排序记录排序次序
 *describe:记录入度 每次筛选入度为0的进入队列 AC 6%
 *2018年6月14日 下午3:31:43
 */
public class CourseScheduleII_210 {

	public static void main(String[] args) {
		CourseScheduleII_210 test=new CourseScheduleII_210();
		System.out.println(test.findOrder(4, new int[][] {{2,0},{1,0},{3,1},{3,2},{1,3}}));

	}
	public int[] findOrder(int numCourses, int[][] prerequisites) {
		int []res=new int[numCourses];
		int[] in = new int[numCourses];  //记录入度
        int count=0;
        for(int i=0;i<prerequisites.length;++i) {
        	++in[prerequisites[i][0]];
        }
        Queue<Integer> queue=new LinkedList<Integer>();
        for(int i=0;i<in.length;++i) {
        	if(in[i]==0)
        		queue.add(i);
        }
        while(!queue.isEmpty()) {
        	int nowIn=queue.poll();
        	res[count]=nowIn;
        	++count;
        	for(int i=0;i<prerequisites.length;++i) {
        		if(prerequisites[i][1]==nowIn) {
        			in[prerequisites[i][0]]--;
        			if(in[prerequisites[i][0]]==0) {
        				queue.add(prerequisites[i][0]);
        			}
        		}
        	}
        }
        return numCourses==count?res:new int[] {};
    }
}
